﻿using System;
using System.Collections.Generic;

namespace Heap {
    /// <summary>
    /// An "ad minimum" heap that allows duplicated elements.
    /// </summary>
    /// <typeparam name="T">The type of the heap elements.</typeparam>
    public interface IHeap<T> : IEnumerable<T> {
        /// <summary>
        /// Find the minimum item
        /// </summary>
        /// <returns>The minimum item of the heap</returns>
        T FindMin();
        /// <summary>
        /// Update a key. If there are multiple values of this key, it will be updated only one occurence. 
        /// </summary>
        /// <param name="oldKey">The old value of the key to be updated</param>
        /// <param name="newKey">The new value of the key</param>
        void ChangeKey(T oldKey, T newKey);
        /// <summary>
        /// Add a new key to the heap.
        /// </summary>
        /// <param name="item">The item to insert into the heap.</param>
        void Insert(T item);
        /// <summary>
        /// Return the number of items in the heap
        /// </summary>
        /// <returns>The number of items in the heap</returns>
        uint Size();
        /// <summary>
        /// Tell if the heap is empty
        /// </summary>
        /// <returns>Returns true if the heap is empty, false otherwise</returns>
        bool IsEmpty();
        /// <summary>
        /// Return the node of minimum value from the min heap after removing it from the heap
        /// </summary>
        /// <returns>The root node of the heap</returns>
        T ExtractMin();
        /// <summary>
        /// Move a node down in the tree, as long as needed
        /// </summary>
        /// <param name="item">The item to move down</param>
        void MoveDown(T item);
        /// <summary>
        /// Move a node up in the tree, as long as needed
        /// </summary>
        /// <param name="item">The item to move up</param>
        void MoveUp(T item);
        /// <summary>
        /// Search for an item in the Heap
        /// </summary>
        /// <param name="item">The item to find into the heap</param>
        /// <returns>True if in the heap there is at least one occurence of the item; false otherwise</returns>
        bool Contains(T item);
    }

    /// <summary>
    /// A factory to create an "ad minimum" Heap
    /// </summary>
    /// <typeparam name="T">The type of the heap elements</typeparam>
    public interface IHeapFactory<T> {
        /// <summary>
        /// Create an empty heap with the order given by the comparer
        /// </summary>
        /// <param name="comparer">The comparer to use to create the heap</param>
        /// <returns>An empty heap</returns>
        IHeap<T> CreateHeap(IComparer<T> comparer);
        /// <summary>
        /// Create a heap out of given collection of elements using the order given by the comparer
        /// </summary>
        /// <typeparam name="T1">The type of the items to add to the heap</typeparam>
        /// <param name="items">The items to add to the heap</param>
        /// <param name="comparer">The comparer to use to create the new heap</param>
        /// <returns>A heap containing all the elements in items</returns>
        IHeap<T> CreateHeap<T1>(IEnumerable<T1> items, IComparer<T> comparer) where T1 : T;

        /// <summary>
        /// Join two heaps to form a valid new heap containing all the elements of both
        /// </summary>
        /// <typeparam name="T1">The type of the elems of the first heap</typeparam>
        /// <typeparam name="T2">The type of the elems of the other heaps</typeparam>
        /// <param name="comparer">The comparer of the new heap used to establish the order among the elements</param>
        /// <param name="heap1">The first heap</param>
        /// <param name="otherHeaps">The other heaps</param>
        /// <returns>An heap with all the items of the two heaps and using the comparer</returns>
        IHeap<T> Merge<T1, T2>(IComparer<T> comparer, IHeap<T1> heap1, params IHeap<T2>[] otherHeaps) where T1 : T where T2 : T;
    }

    /// <summary>
    /// A factory to create an "ad minimum" Heap of IComparable elements.
    /// </summary>
    /// <typeparam name="T">The IComparable type of the elements of the heap</typeparam>
    public interface IHeapFactoryDefault<T> : IHeapFactory<T> where T: IComparable<T> {
        /// <summary>
        /// Create a heap out of given collection of elements using their natural ordering
        /// </summary>
        /// <typeparam name="T1">The type of the items to add to the heap</typeparam>
        /// <param name="items">The items to add to the heap</param>
        /// <returns>A heap containing all the items specified</returns>
        IHeap<T> CreateHeap<T1>(IEnumerable<T1> items) where T1 : T;

        /// <summary>
        /// Create an empty heap using the natual ordering of the type of its elements
        /// </summary>
        /// <returns>An empty heap</returns>
        IHeap<T> CreateHeap();
    }
}